package com.ting.test.algorithms.大厂刷题班;

import java.util.HashMap;

/**
 * 给定一个数组，可以在每个数字之前决定使用+或者-
 * 所有的数据都得参加
 * 给定一个目标数target,
 * 求最终算出targert的方法数
 */
public class 以加或减返回最后算出target的总f方法数 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, -3, 2, 32, 21, -10};
        int target = 10;

        int count = process(arr, target);
    }

    private static int process(int[] arr, int target) {
        if (arr == null) {
            return 0;
        }
        return f(arr, 0, target);
    }

    /**
     * 该方法的含义是是 从数组的index位置出发，能够算出目标数target的方法数
     *
     * @param arr
     * @param index  当前位置
     * @param target 目标数
     */
    private static int f(int[] arr, int index, int target) {

        if (index == arr.length) {
            return target == 0 ? 1 : 0;//如果整个数组已经遍历完，恰好目标数已经为0，则表明该方法是一种正确的方法
        }
        return f(arr, index + 1, target + arr[index]) + f(arr, index + 1, target - arr[index]);

    }


    private static int process2(int[] arr, int target) {
        if (arr == null) {
            return 0;
        }
        HashMap<Integer, HashMap<Integer, Integer>> dpMap = new HashMap<Integer, HashMap<Integer, Integer>>();


        return f2(arr, 0, target, dpMap);
    }


    /**
     * 该方法的含义是是 从数组的index位置出发，能够算出目标数target的方法数
     *
     * @param arr
     * @param index  当前位置
     * @param target 目标数
     */
    private static int f2(int[] arr, int index, int target, HashMap<Integer, HashMap<Integer, Integer>> dp) {

        if (dp.containsKey(index) && dp.get(index).containsKey(target)) {
            return dp.get(index).get(target);
        }

        if (index == arr.length) {
            return target == 0 ? 1 : 0;//如果整个数组已经遍历完，恰好目标数已经为0，则表明该方法是一种正确的方法
        }
        int ans = f(arr, index + 1, target + arr[index]) + f(arr, index + 1, target - arr[index]);

        HashMap<Integer, Integer> integerIntegerHashMap = dp.get(index);
        if (integerIntegerHashMap == null) {
            integerIntegerHashMap = new HashMap<Integer, Integer>();
        }
        integerIntegerHashMap.put(target, ans);
        dp.put(index, integerIntegerHashMap);
        return ans;
    }
}
